An important element for providing advanced telecommunications network services requiring large bandwidth is a high capacity packet switch capable of interconnecting a large number of subscriber lines.
Such a packet should include i input ports (i=1,2,3, . . . ) and j output ports (j=1,2,3 . . . ). Typically, such a packet switch is synchronous and the packets routed therein are of fixed length. During a packet switch cycle, packets present at the i inputs are routed through the packet switch to particular ones of the j outputs. More particularly, for each packet switch cycle, each input port i may attempt delivery of a packet to a certain output port j.
A packet switching network is internally non-blocking if it can deliver all packets from the input ports i, to the requested output ports j when the output ports are distinct for all input ports i making requests. However, an internally, non-blocking switching network can still block if there are two simultaneous requests for the same output port. In this case, one or both packets directed to the same output port will be blocked or destroyed. Thus, a mechanism to resolve output port conflicts in internally non-blocking packet switching networks is required.
An example of an internally non-blocking switching network is the Batcher-Banyan network, which comprises a Batcher sorting network followed by a Banyan routing network. Batcher-Banyan networks are discussed in detail in A. Huang et al. "Starlite: A Wide Band Digital Switch", Proceedings of the 1984 Globecome Conference.
The Batcher-Banyan network is a self routing network which routes a packet from a particular input port to a particular output port based on a destination address in the packet header. It is known that an internally, non-blocking network results by first sorting the packets in non-decreasing order according to the destination address in a sorter network (e.g., a Batcher network) prior to routing the packets through a Banyan network. The Banyan network routes each packet to the particular output port address contained in the packet header. Unfortunately, blocking occurs in the resulting Batcher-Banyan network if more than one packet is addressed to a particular Banyan output port in any given packet switch cycle.
One particular scheme for resolving such output port conflicts is disclosed in the above-identified Huang et al. reference, which reference is directed to the Starlite switch. In the Starlite switch, the packets are routed through a Batcher sorting network and a Banyan routing network. The Batcher network serves to sort the packets in non-decreasing order according to destination (i.e., Banyan output port) address. At the output of the Batcher network, all but one packet addressed to each output port is purged, so that after purging only packets with unique destination addresses remain. Consequently, at the output of the Batcher network the packet destination addresses are in strictly increasing order, but with holes in the sequence due to purged packets. This sequence with holes can cause packet collisions in the subsequent Banyan network. Consequently, a concentration network is required in front of the Banyan network for skewing all packets toward the top to fill in the holes left by the purged packets. Such concentration networks involve rather complex operations such as counting the numbers of packets above a certain output line of the Batcher network. In general, concentration networks may be as complex as the Batcher network in terms of node counts.
In the Starlite switch, in order to deliver the purged packet, the purged packets are routed from the outputs of the Batcher sorting network to some input ports of the switch which are specially dedicated for re-entry of purged packets. To reduce the number of input ports dedicated to re-entry, the purged packets go through a concentration network.
Thus, the above-described output port conflict resolution scheme suffers from the following shortcomings. First, more than half of the input ports are dedicated for re-entering packets. In addition, the remaining input ports must not be loaded above about 40% to prevent excessive packet loss. The Starlite switch requires two concentration networks, with their associated chip sets and subsystem designs. Lastly, packets may be delivered out of sequence using the Starlite conflict resolution scheme.
Accordingly, it is the object of the present invention to provide a simpler, more efficient scheme for resolving output port conflicts in an internally non-blocking packet switching network such as the Batcher-Banyan network.